package com.ztom.dp;

/**
 * 打家劫舍 2
 * <p>
 * https://leetcode-cn.com/problems/house-robber-ii/
 *
 * @author ZhangTao
 */
public class Code06Rob {

    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }

        // 环状, 求 [0, n -2] 与 [1, n - 1] 的大值
        return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
    }

    private int rob(int[] nums, int l, int r) {
        int prepre = nums[l];
        int pre = Math.max(nums[l], nums[l + 1]);
        int res = pre;
        for (int i = l + 2; i <= r; i++) {
            res = Math.max(pre, prepre + nums[i]);
            prepre = pre;
            pre = res;
        }
        return res;
    }
}
